#include <stdio.h>
#include <omp.h>
#include <time.h>
#include <stdlib.h>

// 快速排序算法
void QuickSort(int data[], int low, int high)
{
    if (low >= high)
        return;
    int i = low;
    int j = high;
    int pivot = data[low]; // 以第一个元素作为枢轴
    while (i < j)
    {
        while (i < j && data[j] >= pivot)
            j--;
        data[i] = data[j];
        while (i < j && data[i] <= pivot)
            i++;
        data[j] = data[i];
    }
    data[i] = pivot;
    // 使用OpenMP并行化
    #pragma omp parallel sections
        {
    #pragma omp section
            QuickSort(data, low, i - 1); // 对左边元素快排
    #pragma omp section
            QuickSort(data, i + 1, high); // 对右边元素快排
        }
}

void CreateData(int *arr, int size){
    srand(0);
    for (int i = 0; i < size; ++i)
        arr[i] = rand() % size;
}


int main()
{
    clock_t start, end;
    double total;
    int i;
    start = clock(); // 获取开始时间

    const int DataSize = 1e6;
    int data[DataSize];
    CreateData(data, DataSize);
    QuickSort(data, 0, 9); // 快排
    // for (int i = 0; i < 10; ++i)
    //     printf("%d ", data[i]);
    // printf("\n");

    end = clock();                                  // 获取结束时间
    total = (double)(end - start) / CLOCKS_PER_SEC; // 计算耗时
    printf("Total time: %f seconds\n", total);

    return 0;
}